#include <vector>
using namespace std;
#include <set>
#include <algorithm>


// version 1
//双指针 + Leetcode中有一题(和为s的两个数, Leetcode剑指offer57)做法，时间复杂度O(N^2)
class Solution1 {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //猜测：固定一个数，然后剩下区间内找两数之和
        //前提是有序
        set<vector<int>> s;//用于去重
        std::sort(nums.begin(), nums.end());
        for(int target_i = 0; target_i < nums.size() - 2; ++target_i){
            int target = 0 - nums[target_i];
            int left = target_i + 1, right = nums.size() - 1;
            while(left < right){
                if(nums[left] + nums[right] < target) ++left;
                else if(nums[left] + nums[right] > target) --right;
                else{
                    s.insert({nums[target_i], nums[left], nums[right]});
                    ++left;
                }
            }
        }
        vector<vector<int>> ret(s.begin(), s.end());
        return ret;
    }
};







//version 2  
//不用容器去重
class Solution2 {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        vector<vector<int>> ret;

        //这里还能优化一下，排好序后，只要target_i碰到>0的数，就没必要往后走了！
        //因为后面的数相加不可能是负数！  -> 这里就不写了！！！
        for(int target_i = 0; target_i < nums.size() - 2; ++target_i){
            int target = 0 - nums[target_i];
            int left = target_i + 1, right = nums.size() - 1;

            while(left < right){
                if(nums[left] + nums[right] < target) ++left;
                else if(nums[left] + nums[right] > target) --right;
                else{
                    //左右都把当前相同的给跳过
                    ret.push_back({nums[target_i], nums[left], nums[right]});
                    int leftnum = nums[left], rightnum = nums[right];
                    while(left < right && nums[left] == leftnum) ++left;
                    while(left < right && nums[right] == rightnum) --right;
                }
            }
            //对于target_i来说，也可以进行跳过！
            while(target_i < nums.size() - 2 && nums[target_i + 1] == nums[target_i]) 
                ++target_i;
            
        }
        return ret;
    }
};